<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <script>
            /* 注意：每个数字只能用1次，而且最后结果不能重复,对candidates进行排序
                每次依然是start+1，最后通过map进去去重
            */
            var combinationSum2 = function (candidates, target) {
                candidates.sort((a, b) => a - b)
                let map = new Map()
                let res = []
                function backTacking(path, sum, start) {
                    if (sum > target) return
                    if (sum == target) {
                        let pathStr = path.join("")
                        if (map.has(pathStr)) return
                        map.set(pathStr, 1)
                        return res.push([...path])
                    }
                    for (let i = start; i < candidates.length; i++) {
                        //目前这么写，它会超时，所以我们需要进行剪枝
                        //如 [1,1,1,2] target==3   我们必须保证这一层的i都是从start开始 因此i-1>=start
                        if (i - 1 >= start && candidates[i] == candidates[i - 1]) continue
                        path.push(candidates[i])
                        backTacking(path, sum + candidates[i], i + 1)
                        path.pop()
                    }
                }
                backTacking([], 0, 0)
                return res
            }
        </script>
    </body>
</html>
